// 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

// 示例 1:

// 输入: num1 = "2", num2 = "3"
// 输出: "6"
// 示例 2:

// 输入: num1 = "123", num2 = "456"
// 输出: "56088"
// 说明：

// num1 和 num2 的长度小于110。
// num1 和 num2 只包含数字 0-9。
// num1 和 num2 均不以零开头，除非是数字 0 本身。
// 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

#include <string>
#include <vector>

using namespace std;

/*
多位数的乘法过程，每位相乘然后错位相加
把错位相加后的结果保存到一个一维数组中，然后分别每位上算进位，最后每个数字都变成一位，
然后要做的是去除掉首位0，最后把每位上的数字按顺序保存到结果中即可，代码如下：
*/
class Solution {
public:
    string multiply(string num1, string num2) {
        string res{};
        int n1 = num1.size();
        int n2 = num2.size();
        int k = n1 + n2 - 2;
        int carry{0};              // 进位
        vector<int> v(n1 + n2, 0); // n1位数乘以n2位数的结果最多是n1+n2位
        for (int i{0}; i < n1; ++i) {
            for (int j{0}; j < n2; ++j) {
                v[k - i - j] += (num1[i] - '0') * (num2[j] - '0');
            }
        }
        // 依次计算每一位的进位
        for (int i{0}; i < n1 + n2; ++i) {
            v[i] += carry;
            carry = v[i] / 10;
            v[i] %= 10;
        }
        // 去除前面的0
        int i = n1 + n2 - 1;
        while (v[i] == 0)
            --i;
        if (i < 0)
            return "0";
        while (i >= 0)
            res.push_back(v[i--] + '0');
        return res;
    }
};

/* 做加法
时间复杂度：O(mn + n^2)
空间复杂度：O(m + n)
*/
class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") {
            return "0";
        }
        string res{"0"};
        int m = num1.size();
        int n = num2.size();
        for (int i{n-1}; i >= 0; --i) {
            string cur{};
            int add{0}; // 进位
            for (int j{n-1}; j > i; --j) {
                cur.push_back(0); // 补上0
            }
            int y = num2[i] - '0';
            for (int j{m-1}; j >= 0; --j) {
                int x = num1[j] - '0';
                int product = x*y + add;
                cur.push_back(product % 10);
                add = product / 10;
            }
            while (add != 0) {
                cur.push_back(add % 10);
                add /= 10;
            }
            reverse(cur.begin(), cur.end());
            for (auto& c : cur) { // 把cur中的所有数字变成字母数字
                c += '0';
            }
            res = addStrings(res, cur);
        }
        return res;
    }
    string addStrings(const string& num1, const string& num2) { // LeetCode_415_字符串相加
        string res{};
        int len1 = num1.size();
        int len2 = num2.size();
        int index1 = len1 - 1;
        int index2 = len2 - 1;
        int carry{0}; // 进位
        while (index1 >= 0 || index2 >= 0) {
            int n1 = (index1 >= 0 ? num1[index1] - '0' : 0);
            int n2 = (index2 >= 0 ? num2[index2] - '0' : 0);
            int sum = n1 + n2 + carry;
            carry = sum / 10;
            res = to_string(sum % 10) + res;
            --index1;
            --index2;
        }
        if (carry == 1) {
            res = to_string(carry) + res;
        }
        return res;
    }
};

/* 做乘法
乘积的长度为m+n-1或m+n
时间复杂度：O(mn)
空间复杂度：O(m + n)
*/
class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") {
            return "0";
        }
        int m = num1.size();
        int n = num2.size();
        vector<int> resVec(m + n, 0);
        for (int i{m-1}; i >= 0; --i) {
            int x = num1[i] - '0';
            for (int j{n-1}; j >= 0; --j) {
                int y = num2[j] - '0';
                resVec[i + j + 1] += x * y;
            }
        }
        // 进位
        for (int i{m + n -1}; i > 0; --i) {
            resVec[i - 1] += resVec[i] / 10;
            resVec[i] %= 10;
        }
        int index = (resVec[0] == 0 ? 1 : 0);
        string res{};
        while (index < m + n) {
            res += resVec[index] + '0';
            ++index;
        } 
        return res;
    }
};
